#include<iostream>
#include<algorithm>
#include<vector>
#include<iostream>
#include<utility>
#include<map>
using namespace std;
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '['; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << ']'; }

void debug_out() { cerr << endl; }
template<typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cerr << ' ' << H; debug_out(T...); }

#define show(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)



using job = std::pair<string, int>;
using job_stream = std::vector<job>;
const int threshold = 3;


void revoke(vector<pair<int, int>>&free_pool, vector<pair<int, int>>&busy_pool, int address) {
    pair<int, int>memory_block;
    for (auto it = busy_pool.begin(); it != busy_pool.end(); ++it) {
        if (it -> first == address) {
            memory_block = *it;
            busy_pool.erase(it);
            break;
        }
    }
    for (auto it = free_pool.begin(); it != free_pool.end(); ++it) {
        if ((*it).first + (*it).second == memory_block.first) {
            memory_block.first = (*it).first;
            memory_block.second += (*it).second;
            free_pool.erase(it);
            break;
        }
    }
    for (auto it = free_pool.begin(); it != free_pool.end(); ++it) {
        if ((*it).first == memory_block.first + memory_block.second) {
            memory_block.second += (*it).second;
            free_pool.erase(it);
            break;
        }
    }
    free_pool.push_back(memory_block);
}

void first_fit(job_stream& JS) {
    vector<pair<int, int>>free_pool(1, {0, 1024});
    vector<pair<int, int>>busy_pool;
    map<string, int>address;
    show(free_pool);
    show(busy_pool);
    for (auto& J : JS) {
        sort(free_pool.begin(), free_pool.end(),[](pair<int, int>&p, pair<int, int>&q) {
            return p.first < q.first;
        });
        bool assign_success = false;
        for (auto it = free_pool.begin(); it != free_pool.end(); ++it) {
            if ((*it).second >= J.second) {
                address[J.first] = (*it).first;
                if ((*it).second - J.second > threshold) {
                    busy_pool.push_back({(*it).first, J.second});
                    (*it).first += J.second;
                    (*it).second -= J.second;
                } else {
                    busy_pool.push_back(*it);
                    free_pool.erase(it);
                }
                assign_success = true;
                break;
            }
        }
        if (!assign_success) {
            cerr<<"assign failed"<<endl;
        }
        show(free_pool);
        show(busy_pool);
    }
}

void best_fit(job_stream& JS) {
    vector<pair<int, int>>free_pool(1, {0, 1024});
    vector<pair<int, int>>busy_pool;
    show(free_pool);
    show(busy_pool);
    map<string, int>address;
    for (auto& J : JS) {
        sort(free_pool.begin(), free_pool.end(),[](pair<int, int>&p, pair<int, int>&q) {
            return p.second < q.second;
        });
        bool assign_success = false;
        for (auto it = free_pool.begin(); it != free_pool.end(); ++it) {
            if ((*it).second >= J.second) {
                address[J.first] = (*it).first;
                if ((*it).second - J.second > threshold) {
                    busy_pool.push_back({(*it).first, J.second});
                    (*it).first += J.second;
                    (*it).second -= J.second;
                } else {
                    busy_pool.push_back(*it);
                    free_pool.erase(it);
                }
                assign_success = true;
                break;
            }
        }
        if (!assign_success) {
            cerr<<"assign failed"<<endl;
        }
        show(free_pool);
        show(busy_pool);
    }
}

void worst_fit(job_stream& JS) {
    vector<pair<int, int>>free_pool(1, {0, 1024});
    vector<pair<int, int>>busy_pool;
    show(free_pool);
    show(busy_pool);
    map<string, int>address;
    for (auto& J : JS) {
        sort(free_pool.begin(), free_pool.end(),[](pair<int, int>&p, pair<int, int>&q) {
            return p.second > q.second;
        });
        bool assign_success = false;
        for (auto it = free_pool.begin(); it != free_pool.end(); ++it) {
            if ((*it).second >= J.second) {
                address[J.first] = (*it).first;
                if ((*it).second - J.second > threshold) {
                    busy_pool.push_back({(*it).first, J.second});
                    (*it).first += J.second;
                    (*it).second -= J.second;
                } else {
                    busy_pool.push_back(*it);
                    free_pool.erase(it);
                }
                assign_success = true;
                break;
            }
        }
        if (!assign_success) {
            cerr<<"assign failed"<<endl;
        }
        show(free_pool);
        show(busy_pool);
    }
}

int main() {
    job_stream V{{"abc", 205}, {"def", 200}, {"ghi", 305}};
    first_fit(V);
    best_fit(V);
    worst_fit(V);
    return 0;
}

